1. Field of the Invention
The present invention relates to decoding of encoded data by a receiver in a telecommunication network, and, more particularly, to reducing the number of iterations of an iterative decoder.
2. Description of the Related Art
Many communication systems employ 1) multi-dimensional encoding of data with convolutional codes and 2) iterative decoding of the encoded data due to the relatively high coding gain and simple structure of an iterative decoder. Iterative decoding methods may employ xe2x80x9csoft-in, soft-outxe2x80x9d decoders for decoding data. In an iterative decoding scheme, encoded data is repetitively decoded until a predetermined number of decoding iterations complete.
The following may be of use to understand the encoding and decoding methods. A set of binary values u is defined in the Galois field-2(GF(2)) with elements {+1, xe2x88x921} where xe2x88x921 is the xe2x80x9cnullxe2x80x9d element under modulo-2 addition. The reliability value, or soft value, L(u) is the log-likelihood ratio of the binary random values in U and is defined as the (natural) log of the ratio of the probability that the random variable U takes on the value u=+1 (logic 2) to the probability that the random variable U takes on the value u=xe2x88x921 (logic 0). The sign of L(u) is used as a hard decision by a detector or decoder, and the magnitude of L(u) is used as a reliability statistic (value) for the hard decision.
In an iterative decoding scheme, the reliability values based on the information bits are updated at each iteration, utilizing the information extracted from the previous iteration. Decoding produces a posteriori reliability values for the output, decoded data. The a priori reliability values may either be the null set (logic 0 or 1, depending on definition) for the first iteration (since there is no a priori information) or, after the first iteration, extrinsic reliability values for the information bits from a previous iteration. The extrinsic reliability values are values based on indirect information contained in the decoded information bits, and may be generated from the a posteriori reliability values. In general, the a posteriori reliability values and/or the extrinsic reliability values of an iteration are employed as extrinsic information input to a decoder for decoding data during the next iteration.
FIG. 1 shows an iterative decoder 100 as may be employed in a turbo decoder of the prior art operating in accordance with, for example, the CDMA-2000 standard. The iterative decoder receives encoded data that may be formed as follows. A frame of data is encoded with a first block code and a first parity bit XP1 is added to the encoded frame of data. The frame of data is also interleaved with mapping f(*) and encoded with a second block code (which may be equivalent to the first block code), and a second parity bit XP2 is added to the encoded frame of data. The encoded data is combined with the interleaved and encoded data to form a set of systematic bits XS (e.g., using a product code).
The iterative decoder includes first and second decoders 101 and 104, interleavers 102 and 109 each applying the mapping f(*) to input data, de-interleaver 106 applying the inverse of the mapping f(*) to input data, and optional buffers 103, 105, 107, 108, and 110 used to temporarily store values during the decoding process. First and second decoders 101 and 104 apply respective decoding operations D1 (the inverse of the first block code) and D2 (the inverse of the second block code).
The iterative decoder completes one iteration as follows. First decoder 101 receives systematic bits XS (via 111) and parity bits XP1 (via 112) of the received frame from, for example, an external memory 120. First decoder 101 also receives extrinsic information (e.g., both the reliability values (soft-data representing values for the decoded frame of data) and extrinsic reliability values) from buffer 107 (via 114). Extrinsic information for one decoder may be derived from the de-interleaved, decoded frame of data from the other decoder and parity bits XP1 and/or and parity bits XP2. For the first iteration, the extrinsic information provided to first decoder 101 may be initialized to the null set (logic 0 or 1, depending on definition). First decoder 101 performs decoding operation D1 on the systematic bits XS using the extrinsic information and parity bits XP1 to generate soft data. The soft data from first decoder 101 is then interleaved by interleaver 109, and the interleaved soft data is provided as extrinsic information for second decoder 104 (via 115). Systematic bits XS are also interleaved by interleaver 102.
Second decoder 104 receives the interleaved extrinsic information (via 115), the parity bits XP2 (via 113), and the interleaved systematic bits XS (via 116), and performs decoding operation D2 to generate soft data. The soft data from second decoder 104 is then de-interleaved by de-interleaver 106 and provided as the extrinsic information (via 114) for decoding the systematic bits XS in the next iteration by first decoder 101, thus ending a single iteration of decoder 100. Several iterations may be required to generate a decoded frame of data from the systematic bits XS and parity bits XP1 and XP2 to satisfy a predetermined threshold for bit error rate (BER) of the iterative decoder. Half of an iteration is defined to be all the operations around one of the two decoders 101 and 104.
After N iterations, the turbo decoder combines the extrinsic information from both decoders 101 and 104 with the systematic bits XS from the received frame to form the so called soft outputs against which the decision on the transmitted bits are made. In this iteration process, every frame of encoded data requires N iterations to decode, thus the number of computations is fixed. In general, more iterations of the iterative decoding process result in a lower bit error rate (BER) for the decoded output data. For typical implementations of the prior art turbo decoder of FIG. 1, 10 to 20 iterations may be needed for satisfactory BER of a decoded frame when signal-to-noise ratio (SNR) is low. Since the number of computations of a circuit implementing the iterative decoder is directly proportional to the number of iterations required for decoding, more iterations generally result in higher power consumption for the circuit. Consequently, improving the BER performance of the circuit is generally achieved at the expense of increased power consumption.
FIG. 2 shows simulated turbo decoder performance as BER versus SNR for different numbers of iterations for the iterative decoder of FIG. 1. The signals are modulated, encoded frames of 20,730 bits that are transmitted through a communication channel adding white, Gaussian noise to the signal. Referring to FIG. 2, higher numbers of iterations generally result in lower BER for the decoded frame. For relatively high SNR (greater than 0.9 dB in FIG. 2), a point (number of iterations) exists where more iterations do not necessarily result in lower BER. Typical choices for the total number N of decoding iterations are generally between 8 and 12 iterations for moderate to high SNR. However, the iterative decoding process may exhibit abnormalities when higher numbers of iterations are employed. For example, a plot of the BER curve versus number of iterations may not be monotonically decreasing (i.e., the BER may actually be worse with more iterations); and (ii) given a fixed number of iterations, BER may not be monotonically decreasing with the SNR of the input signal. Pathetic decoded frames of data in which errors may grow with more iterations cause the BER abnormality.
Methods of the prior art to reduce the number of computations, and hence the power consumption in the particular circuit implementation of the iterative decoder, focus on comparing the decoded output of two consecutive iterations, or occasionally two half iterations. If the decoded output data for the two iterations are xe2x80x9csufficiently closexe2x80x9d to each other (according to a predefined measure), then the iterative decoding process may be terminated. Such predefined measure may simply be a total difference in decoded bits between frames being less than a predefined threshold that provides as error bound in the data of the decoded frame. However, some measures of xe2x80x9csufficiently closexe2x80x9d require sophisticated mathematical computation, increasing the number of computations required. Second, these prior art approaches require two decoded output frames for a decision. Thus, even if an iteration produces the correctly decoded frame, an iterative decoder must wait for the result of the next iteration to xe2x80x9cconfirmxe2x80x9d this event, resulting in unnecessary computations. Third, some measures of xe2x80x9csufficiently closexe2x80x9d may still make an incorrect decision: a decoded frame of data containing errors may pass the xe2x80x9csufficiently closexe2x80x9d test, even though the encoded frame would be correctly decoded after further iterations. For some telecommunication standards, such as 3G wireless standards, cyclic redundancy check (CRC) error correction codes are embedded into encoded data frames. While the CRC codes are employed to detect when a decoded frame includes an error, the error detection code in these applications is not employed for the early termination of iterative decoding. The CRC codes employed by the standards have at most 16 bits, which is not sufficient to keep the probability of the error event low if used as a measure for early termination of iterative decoding.
The present invention relates to iterative decoding of an encoded frame of data that includes error detection information employed for tests allowing early termination of iterative decoding. A parity check test for the decoded frame is calculated for the decoded frame and, for the first test, iterative decoding is terminated if the decoded frame is declared correct. In addition, the difference, or number of differently decoded bits, between decoded frames of two iterations may be tracked after iterative decoding reaches an intermediate iteration threshold. A test determines a coding iteration for which the tracked difference has a relative minimum value. For example, the test may track each difference value and select as output, decoded frame of data the decoded frame corresponding to the iteration having the minimum difference value. Alternatively, the test may determine whether, for a particular iteration, the difference as a function of iteration is no-longer monotonically decreasing. If, after an iteration, the number of differently decoded bits is not monotonically decreasing, iterative decoding is terminated. Implementations of the present invention reduce or eliminate i) unnecessary computations during iterative decoding, and ii) the BER abnormality caused by high numbers of decoding iterations.
In accordance with embodiments of the present invention, decoding of an encoded frame comprises decoding the encoded frame during a current iteration of iterative decoding to provide a decoded frame including decoded data and decoded error detection information. A parity value is calculated from the decoded data, and the parity value is compared with the decoded error detection information to determine if the data passes a parity check. If the decoded data passes the parity check, iterative decoding is terminated to provide the decoded data of the current iteration. Otherwise if the decoded data does not pass the parity check, a difference of errors between the decoded frame of the current iteration and a decoded frame of a previous iteration is calculated and iterative decoding is terminated in accordance with an error rate measure. The error rate measure employs the difference calculated for the decoded frame of the current iteration, wherein the error-rate measure indicates either i) achieving a relative minimum difference value or a relative maximum bound for bit-error rate, or a relative minimum in bit-error-rate for iterative decoding between the previous and current iterations.
In accordance with other embodiments of the present invention, decoding of an encoded frame comprises decoding, during a current iteration of iterative decoding, the encoded frame to provide a decoded frame of data. A difference between the decoded frame of the current iteration and a decoded frame of a previous iteration is calculated, the difference related to the number of errors in the decoded frame of the current iteration. Iterative decoding is terminated based on an error rate measure by comparing the difference calculated for the decoded frame of the current iteration with a difference calculated during the previous iteration, wherein the difference calculated during the previous iteration is related to the number of errors in the decoded frame of the previous iteration.